import bisect
from typing import List


class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0

        n = len(nums)

        def bisect_low(target):
            l = 0
            r = n - 1
            while l <= r:
                mid = (l + r) >> 1
                if nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return l - 1

        for i in range(n):
            for j in range(i + 1, n):
                high = nums[j] + nums[i]
                h = bisect_low(high)
                ans += h - j
        return ans


if __name__ == '__main__':
    s = Solution()
    r = s.triangleNumber(
        [4, 2, 3, 4]
    )
    print(r)
